#ifndef BOOKS_CODE_WINDOWS_SKIPLIST_H_
#define BOOKS_CODE_WINDOWS_SKIPLIST_H_

#include "pch.h"
#include "simple_random.h"

static constexpr double kSkipListCoefficient = 0.25;  // 随机系数
static constexpr double kSkipListRandomLimit = kSkipListCoefficient * 0xFFFF;
static constexpr int32_t kSkipListLevelMax   = 32;  // 跳表最大高度限制

template <typename, typename>
class SkipListNode;

/**
 * 跳表上层索引节点
 */
template <typename Key, typename T>
class SkipListLevelNode {
 public:
  using key_type   = Key;
  using value_type = T;
  using node_type  = SkipListNode<Key, T>;

  SkipListLevelNode() = default;

 public:
  std::weak_ptr<node_type> forward_;  // 后置节点
  uint32_t span_{0};                  // 与后置节点的距离
};

template <typename Key, typename T>
using SkipListLevelVec = std::vector<SkipListLevelNode<Key, T>>;

/**
 * 跳表底层节点
 */
template <typename Key, typename T>
class SkipListNode {
 public:
  using key_type   = Key;
  using value_type = T;
  using node_type  = SkipListNode<Key, T>;

  explicit SkipListNode(Key key, T val, int32_t level)
      : key_(key), val_(val), levels_(level, SkipListLevelNode<Key, T>()) {}

 public:
  Key key_;                                       // 键
  T val_;                                         // 值
  std::shared_ptr<node_type> backward_{nullptr};  // 底层回溯节点
  SkipListLevelVec<Key, T> levels_;               // 上层索引
};

/**
 * 跳表
 */
template <typename Key, typename T, typename Compare = std::less<Key>>
class SkipList {
 public:
  using key_type    = Key;
  using value_type  = T;
  using key_compare = Compare;
  using node_type   = SkipListNode<Key, T>;

  SkipList() : length_(0), curr_level_(1), compare_() {
    header_ = std::make_shared<node_type>(Key(), T(), kSkipListLevelMax);
  }

  std::shared_ptr<node_type> Insert(Key key, T val) {
    uint32_t rank[kSkipListLevelMax];
    std::vector<std::shared_ptr<node_type>> path(kSkipListLevelMax, nullptr);

    auto node = header_;
    for (auto i = curr_level_ - 1; i >= 0; --i) {
      rank[i]           = (i == curr_level_ - 1) ? 0 : rank[i + 1];
      auto forward_node = node->levels_[i].forward_.lock();
      while (forward_node) {
        if (compare_(forward_node->key_, key) ||
            (forward_node->key_ == key && forward_node->val_ < val)) {
          rank[i] += node->levels_[i].span_;
          node         = forward_node;
          forward_node = node->levels_[i].forward_.lock();
        } else {
          break;
        }
      }
      path[i] = node;
    }

    int32_t level = RandomLevel();
    if (level > curr_level_) {
      for (auto i = curr_level_; i < level; ++i) {
        rank[i]                   = 0;
        path[i]                   = header_;
        path[i]->levels_[i].span_ = length_;
      }
      curr_level_ = level;
    }

    node = std::make_shared<SkipListNode<Key, T>>(key, val, level);
    for (auto i = 0; i < level; ++i) {
      node->levels_[i].forward_    = path[i]->levels_[i].forward_;
      path[i]->levels_[i].forward_ = node;

      node->levels_[i].span_ = path[i]->levels_[i].span_ - (rank[0] - rank[i]);
      path[i]->levels_[i].span_ = (rank[0] - rank[i]) + 1;
    }

    for (auto i = level; i < curr_level_; ++i) {
      ++path[i]->levels_[i].span_;
    }

    node->backward_ = (path[0] == header_) ? nullptr : path[0];
    if (auto forward_node = node->levels_[0].forward_.lock()) {
      forward_node->backward_ = node;
    } else {
      tail_ = node;
    }
    ++length_;
    return node;
  }

  bool Erase(Key key, T val) {
    std::vector<std::shared_ptr<node_type>> path(kSkipListLevelMax, nullptr);
    auto node = header_;
    for (auto i = curr_level_ - 1; i >= 0; --i) {
      auto forward_node = node->levels_[i].forward_.lock();
      while (forward_node) {
        if (compare_(forward_node->key_, key) ||
            (forward_node->key_ == key && forward_node->val_ < val)) {
          node         = forward_node;
          forward_node = node->levels_[i].forward_.lock();
        } else {
          break;
        }
      }
      path[i] = node;
    }

    node = node->levels_[0].forward_.lock();
    if (node && key == node->key_ && val == node->val_) {
      for (auto i = 0; i < curr_level_; ++i) {
        if (auto forward_node = path[i]->levels_[i].forward_.lock();
            forward_node == node) {
          path[i]->levels_[i].span_ += node->levels_[i].span_ - 1;
          path[i]->levels_[i].forward_ = node->levels_[i].forward_;
        } else {
          --path[i]->levels_[i].span_;
        }

        if (auto forward_node = node->levels_[0].forward_.lock()) {
          forward_node->backward_ = node->backward_;
        } else {
          tail_ = node->backward_;
        }
        while (curr_level_ > 1 &&
               !header_->levels_[curr_level_ - 1].forward_.lock()) {
          --curr_level_;
        }
        --length_;
      }
      return true;
    }

    return false;
  }

 public:
  void Print() {
    std::cout << "len : " << length_ << std::endl;
    std::cout << "level : " << curr_level_ << std::endl;
    std::cout << "++++++++++++++++++++" << std::endl;

    for (auto i = 0; i < curr_level_; ++i) {
      std::cout << "level " << i << std::endl;
      std::cout << "====================" << std::endl;
      auto node = header_->levels_[i].forward_.lock();
      while (node) {
        std::cout << "[" << node->key_ << ":" << node->val_ << "]  ====>  ";
        node = node->levels_[i].forward_.lock();
      }
      std::cout << std::endl;
      std::cout << std::endl;
    }
  }

 private:
  static inline int32_t RandomLevel();

 private:
  std::shared_ptr<node_type> header_{nullptr};  // 跳表头结点
  std::shared_ptr<node_type> tail_{nullptr};    // 跳表尾结点
  uint32_t length_{0};                          // 跳表长度
  int32_t curr_level_{0};                       // 跳表当前高度
  Compare compare_;                             // 比较函数
};

template <typename Key, typename T, typename Compare>
inline int32_t SkipList<Key, T, Compare>::RandomLevel() {
  int32_t level = 1;
  while ((RandI32() & 0xFFFF) < (kSkipListRandomLimit)) {
    ++level;
  }
  return (level < kSkipListLevelMax) ? level : kSkipListLevelMax;
}

#endif  // BOOKS_CODE_WINDOWS_SKIPLIST_H_
